Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science. Let be a set of elements and a positive integer. The Hamming graph has vertex set , the set of ordered - of elements of , or sequences of length from . Two vertices are adjacent if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph is, equivalently, the Cartesian product of .[.]
In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.[.] Unlike the Hamming graphs , the graphs in this more general class are not necessarily distance-regular, but they continue to be regular graph and vertex-transitive.
Special cases
-
, which is the generalized quadrangle
[. See in particular note (e) on p. 300.]
-
, which is the complete graph
[.]
-
, which is the lattice graph and also the rook's graph
[.]
-
, which is the singleton graph
-
, which is the hypercube graph .
-
Because Cartesian products of graphs preserve the property of being a unit distance graph,
Applications
The Hamming graphs are interesting in connection with error-correcting codes
[.] and association schemes,
[. On p. 224, the authors write that "a careful study of completely regular codes in Hamming graphs is central to the study of association schemes".] to name two areas. They have also been considered as a communications network topology in distributed computing.
Computational complexity
It is possible in
linear time to test whether a graph is a Hamming graph, and in the case that it is, find a labeling of it with tuples that realizes it as a Hamming graph.
External links
